﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0072_Connect2 : IAlgorithm
    {
        // 117. 填充每个节点的下一个右侧节点指针 II

        // 给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        // 初始状态下，所有 next 指针都被设置为 NULL。

        // 提示：
        //  树中的节点数小于 6000
        //  -100 <= node.val <= 100

        // 进阶：
        //  你只能使用常量级额外空间。
        //  使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public Node Connect(Node root)
        {
            if (root == null)
                return root;
            var queue = new Queue<Node>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                int size = queue.Count;
                for (int i = 0; i < size; i++)
                {
                    var temp = queue.Dequeue();
                    if (i < size - 1)
                        temp.next = queue.Peek();
                    if (temp.left != null)
                        queue.Enqueue(temp.left);
                    if (temp.right != null)
                        queue.Enqueue(temp.right);
                }
            }
            return root;
        }

        // 进阶，空间负责度为常量
        public Node Connect1(Node root)
        {
            if (root == null)
                return root;
            //cur我们可以把它看做是每一层的链表
            Node cur = root;
            while (cur != null)
            {
                //遍历当前层的时候，为了方便操作在下一
                //层前面添加一个哑结点（注意这里是访问
                //当前层的节点，然后把下一层的节点串起来）
                Node dummy = new Node(0);
                //pre表示访下一层节点的前一个节点
                Node pre = dummy;
                //然后开始遍历当前层的链表
                while (cur != null)
                {
                    if (cur.left != null)
                    {
                        //如果当前节点的左子节点不为空，就让pre节点
                        //的next指向他，也就是把它串起来
                        pre.next = cur.left;
                        //然后再更新pre
                        pre = pre.next;
                    }
                    //同理参照左子树
                    if (cur.right != null)
                    {
                        pre.next = cur.right;
                        pre = pre.next;
                    }
                    //继续访问这一行的下一个节点
                    cur = cur.next;
                }
                //把下一层串联成一个链表之后，让他赋值给cur，
                //后续继续循环，直到cur为空为止
                cur = dummy.next;
            }
            return root;
        }
    }
}
